考纲内容

1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
3. 栈和队列的链式存储结构
4. 多维数组的存储
5. 特殊矩阵的压缩存储
6. 栈、队列和数组的应用

知识框架

3.1 栈和队列的定义和特点

栈的定义和特点

栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。

栈又称为后进先出（Last In First Out，LIFO）的线性表。

栈的数学性质（卡特兰（Catalan）数）：n个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n+1}C_{2n}^n$ 。

3.2 案例引入

案例3.1：数制的转换

---

十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
N=(N div d) × d+N mod d（其中，div为整除运算，mod为求余运算）
例如：(1348)10=(2504)8，其运算过程如下：

假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。上述计算过程是从低位到高位顺序产生八进制数的各个数位；而输出过程应从高位到低位进行，恰好和计算过程相反，因而我们可以使用栈来解决这个问题。在计算过程中依次将得到的余数压入栈中，计算完毕后，再依次弹出栈中的余数就是数制转换的结果。

---

案例3.2：括号匹配的检验。

---

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［(［］［］)］等为正确的格式，［（］或（［（））或（（）］）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如，考虑下列括号序列：

当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，显然第二个括号的期待急迫性高于第一个括号，此时第一个括号“［”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号“）”的出现。类似地，因等来的是第三个括号“［”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号。在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。

---

3.3 栈的表示和操作的实现

3.3.1 栈的类型定义

ADT Stack｛
  数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
  数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n｝
            约定an端为栈顶，a1端为栈底。
  基本操作：
    InitStack(&S) 
      操作结果：构造一个空栈S。 
    DestroyStack(&S) 
      初始条件：栈S已存在。 
      操作结果：栈S被销毁。 
    ClearStack(&S) 
      初始条件：栈S已存在。 
      操作结果：将S清为空栈。 
    StackEmpty(S) 
      初始条件：栈S已存在。 
      操作结果：若栈S为空栈，则返回true，否则返回false。 
    StackLength(S) 
      初始条件：栈S已存在。 
      操作结果：返回S的元素个数，即栈的长度。 
    GetTop(S) 
      初始条件：栈S已存在且非空。 
      操作结果：返回S的栈顶元素，不修改栈顶指针。 
    Push(&S,e) 
      初始条件：栈S已存在。 
      操作结果：插入元素e为新的栈顶元素。 
    Pop(&S,&e) 
      初始条件：栈S已存在且非空。 
      操作结果：删除S的栈顶元素，并用e返回其值。 
    StackTraverse(S) 
      初始条件：栈S已存在且非空。 
      操作结果：从栈底到栈顶依次对S的每个数据元素进行访问。 
}ADT Stack

3.3.2 顺序栈的表示和实现

顺序栈的定义

//- - - - - 顺序栈的存储结构- - - - -
#define MAXSIZE 100             //顺序栈存储空间的初始分配量
typedef struct
{
   SElemType *base;             //栈底指针
   SElemType *top;              //栈顶指针
   int stacksize;               //栈可用的最大容量
}SqStack；

tips：说明

---

（1）base为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此，栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。
（2）stacksize指示栈可使用的最大容量，后面算法3.1的初始化操作为顺序栈动态分配MAXSIZE大小的数组空间，将stacksize置为MAXSIZE。 图3.3 栈中元素和栈指针之间的关系

---

初始化

Status InitStack(SqStack &S)
{//构造一个空栈S
   S.base=new SElemType[MAXSIZE]；               //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
   if(!S.base) exit(OVERFLOW);                  //存储分配失败
   S.top=S.base;                                //top初始为base，空栈
   S.stacksize=MAXSIZE;                         //stacksize置为栈的最大容量MAXSIZE
   return OK;
}

入栈

Status Push(SqStack &S，SElemType e)
{//插入元素e为新的栈顶元素
   if(S.top-S.base==S.stacksize) return ERROR；         //栈满
   *S.top++=e；                                         //元素e压入栈顶，栈顶指针加1
   return OK；
}

出栈

Status Pop(SqStack &S,SElemType &e)
{删除S的栈顶元素，用e返回其值
   if(S.top==S.base) return ERROR;              //栈空
   e=*--S.top;                                  //栈顶指针减1，将栈顶元素赋给e
   return OK;
}

取栈顶元素

SElemType GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针
   if(S.top！=S.base)                    //栈非空
      return *(S.top-1);                //返回栈顶元素的值，栈顶指针不变
}

链栈的表示和实现

链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示，如图3.4所示。链栈的结点结构与单链表的结构相同，在此用StackNode表示，定义如下：

图3.4 链栈示意图

链栈的初始化

Status InitStack(LinkStack &S)
{//构造一个空栈S，栈顶指针置空
   S=NULL;
   return OK;
}

链栈的入栈

Status Push(LinkStack &S, SElemType e)
{//在栈顶插入元素e
   p=new StackNode;                             //生成新结点
   p->data=e;                                   //将新结点数据域置为e
   p->next=S;                                   //将新结点插入栈顶
   S=p;                                         //修改栈顶指针为p
   return OK;
}

链栈的出栈

Status Pop(LinkStack &S,SElemType &e)
{//删除S的栈顶元素，用e返回其值
   if(S==NULL) return ERROR;                            //栈空
   e=S->data;                                           //将栈顶元素赋给e
   p=S;                                                 //用p临时保存栈顶元素空间，以备释放
   S=S->next;                                           //修改栈顶指针
   delete p;                                            //释放原栈顶元素的空间
   return OK;
}

取链栈的栈顶元素

SElemType GetTop(LinkStack S)
{//返回S的栈顶元素，不修改栈顶指针
   if(S！=NULL)                  //栈非空
      return S->data;           //返回栈顶元素的值，栈顶指针不变
}

遍历输出链表中各个结点的递归算法

void TraverseList(LinkList p)
{
   if(p==NULL) return;                      //递归终止
   else
   {
     cout<<p->data<<endl;                   //输出当前结点的数据域
     TraverseList(p->next);                //p指向后继结点继续递归
   }
}

可以简化为：

void TraverseList(LinkList p)
{
   if(p)
   {
     cout<<p->data<<endl;
     TraverseList(p->next);
   }
}

队列的表示和操作的实现

队列的类型定义

ADT Queue {
  数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
  数据关系：R={<ai−1,ai>|ai−1,ai∈D,i=2,…,n}
            约定其中a1端为队列头，an端为队列尾。
  基本操作：
    InitQueue(&Q) 
      操作结果：构造一个空队列Q。 
    DestroyQueue(&Q) 
      初始条件：队列Q已存在。 
      操作结果：队列Q被销毁，不再存在。 
    ClearQueue(&Q) 
      初始条件：队列Q已存在。 
      操作结果：将Q清为空队列。 
    QueueEmpty(Q) 
      初始条件：队列Q已存在。 
      操作结果：若Q为空队列，则返回true，否则返回false。 
    QueueLength(Q) 
      初始条件：队列Q已存在。 
      操作结果：返回Q的元素个数，即队列的长度。 
    GetHead(Q) 
      初始条件：Q为非空队列。 
      操作结果：返回Q的队头元素。 
    EnQueue(&Q,e) 
      初始条件：队列Q已存在。 
      操作结果：插入元素e为Q的新的队尾元素。 
    DeQueue(&Q,&e) 
      初始条件：Q为非空队列。 
      操作结果：删除Q的队头元素，并用e返回其值。 
    QueueTraverse(Q) 
      初始条件：Q已存在且非空。 
      操作结果：从队头到队尾，依次对Q的每个数据元素访问。 
}ADT Queue

队列的顺序存储结构表示如下：

//- - - - - 队列的顺序存储结构- - - - -
#define MAXQSIZE 100            //队列可能达到的最大长度
typedef struct
{
   QElemType *base;             //存储空间的基地址
   int front;                   //头指针
   int rear;                    //尾指针
}SqQueue;

tips：“假溢出”

---

初始化创建空队列时，令front=rear=0，每当插入新的队列尾元素时，尾指针rear增1；每当删除队列头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图3.12所示。
图3.12 顺序分配的队列中头、尾指针和元素之间的关系
假设当前队列分配的最大空间为6，则当队列处于图3.12（d）所示的状态时不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。怎样解决这种“假溢出”问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，如图3.13所示，称之为循环队列。
图3.13 循环队列示意图
头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1”的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。
在图3.14（a）中，队头元素是J5，在元素J6入队之前，在Q.rear的值为5，当元素J6入队之后，通过“模”运算，Q.rear=(Q.rear+1)%6，得到Q.rear的值为0，而不会出现图3.12（d）的“假溢出”状态。
图3.14 循环队列中头、尾指针和元素之间的关系
在图3.14（b）中，J7、J8、J9、J10相继入队，则队列空间均被占满，此时头、尾指针相同。
在图3.14（c）中，若J5和J6相继从图3.14（a）所示的队列中出队，使队列此时呈“空”的状态，头、尾指针的值也是相同的。
由此可见，对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。在这种情况下，如何区别队满还是队空呢？通常有以下两种处理方法。
（1）少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是：
队空的条件：Q.front==Q.rear
队满的条件：(Q.rear+1)%MAXQSIZE==Q.front
如图3.14（d）所示，当J7、J8、J9进入图3.14（a）所示的队列后，(Q.rear+1)%MAXQSIZE的值等于Q.front，此时认为队满。
（2）另设一个标志位以区别队列是“空”还是“满”。

---

循环队列的初始化

Status InitQueue(SqQueue &Q)
{//构造一个空队列Q
   Q.base=new QElemType[MAXQSIZE];              //为队列分配一个最大容量为MAXQSIZE的数组空间
   if(!Q.base) exit(OVERFLOW);                  //存储分配失败
   Q.front=Q.rear=0;                            //头指针和尾指针置为零，队列为空
   return OK;
}

求循环队列的长度

int QueueLength(SqQueue Q)
{//返回Q的元素个数，即队列的长度
   return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

循环队列的入队

Status EnQueue(SqQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
   if((Q.rear+1)%MAXQSIZE==Q.front)             //尾指针在循环意义上加1后等于头指针，表明队满
     return ERROR;
   Q.base[Q.rear]=e;                           //新元素插入队尾
   Q.rear=(Q.rear+1)%MAXQSIZE;                 //队尾指针加1
   return OK；
}

循环队列的出队

Status DeQueue(SqQueue &Q,QElemType &e)
{//删除Q的队头元素，用e返回其值
   if(Q.front==Q.rear) return ERROR;            //队空
   e=Q.base[Q.front];                           //保存队头元素
   Q.front=(Q.front+1)%MAXQSIZE;                //队头指针加1
   return OK;
}

取循环队列的队头元素

SElemType GetHead(SqQueue Q)
{//返回Q的队头元素，不修改队头指针
   if(Q.front!=Q.rear)                   //队列非空
     return Q.base[Q.front];             //返回队头元素的值，队头指针不变
}

链队——队列的链式表示和实现

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，如图3.15所示。一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。队列的链式存储结构表示如下：

//- - - - - 队列的链式存储结构- - - - -
typedef struct QNode
{
   QElemType data;
   struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
   QueuePtr  front;                             //队头指针
   QueuePtr  rear;                              //队尾指针
}LinkQueue;

链队的初始化

Status InitQueue(LinkQueue &Q)
{//构造一个空队列Q
   Q.front=Q.rear=new QNode;            //生成新结点作为头结点，队头和队尾指针指向此结点
   Q.front->next=NULL;                  //头结点的指针域置空
   return OK;
}

链队的入队

tips：图3.16 队列运算指针变化状况

---

---

Status EnQueue(LinkQueue &Q,QElemType e)
{//插入元素e为Q的新的队尾元素
   p=new QNode;                                 //为入队元素分配结点空间，用指针p指向
   p->data=e;                                   //将新结点数据域置为e
   p->next=NULL; Q.rear->next=p;                //将新结点插入到队尾
   Q.rear=p;                                    //修改队尾指针
   return OK;
}

链队的出队

Status DeQueue(LinkQueue &Q,QElemType &e)
{//删除Q的队头元素，用e返回其值
   if(Q.front==Q.rear) return ERROR;               //若队列空，则返回ERROR
   p=Q.front->next;                                //p指向队头元素
   e=p->data;                                      //e保存队头元素的值
   Q.front->next=p->next;                          //修改头结点的指针域
   if(Q.rear==p) Q.rear=Q.front;                  //最后一个元素被删，队尾指针指向头结点
   delete p;                                      //释放原队头元素的空间
   return OK;
}

需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。

取链队的队头元素。

SElemType GetHead(LinkQueue Q)
{//返回Q的队头元素，不修改队头指针
   if(Q.front!=Q.rear)                                   //队列非空
     return Q.front->next->data;                        //返回队头元素的值，队头指针不变
}

表3.3 栈和队列的比较

习题

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现（ ）的情况。

A. 5，4，3，2，1

B. 2，1，5，4，3

C. 4，3，1，2，5

D. 2，3，5，4，1

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

A. i

B. n-i

C. n-i+1

D. 不确定

（ 3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾 元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（） 。 A ． r-f B ． (n+f-r)%n C ． n+r-f D ．( n+r-f)%n

（4）链式栈结点为（data，link），top指向栈顶，若想摘除栈顶结点，并将删除结点的值保存到x中，则应执行操作（ ）。 A. x=top->data;top=top->link； B. top=top->link;x=top->link； C. x=top;top=top->link； D. x=top->link；

（5）设有一个递归算法如下：

int fact(int n)
{//n大于等于0
   if(n<=0) return 1;
   else return n*fact(n-1);
}

则计算fact(n)需要调用该函数的次数为（ ）。

A. n+1

B. n-1

C. n

D. n+2

（6）栈在（ ）中有所应用。 A. 递归调用 B. 函数调用 C. 表达式求值 D. 前三个选项都有

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 队列
B. 栈
C. 线性表
D. 有序表

（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ ）。

A. 2

B. 3

C. 4

D. 6

（9）若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。
A. top++; V[top]=x;
B. V[top]=x; top++;
C. top--; V[top]=x;
D. V[top]=x; top--;

（11）用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A. rear=rear+1
B. rear=(rear+1)%(m-1)
C. rear=(rear+1)%m
D. rear=(rear+1)%(m+1)

（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A. (rear+1)%n==front
B. rear==front
C. rear+1==front
D. (rear-l)%n==front

（14）栈和队列的共同点是（ ）。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点

（15）一个递归算法必须包括（ ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分

2．算法设计题

（1）将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长（见图3.17）。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下:

typedef struct
{
   int top[2], bot[2];                  //栈顶和栈底指针
   SElemType *V;                        //栈数组
   int m;                              //栈最大可容纳元素个数
}DblStack;

[ 题目分析 ]
两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为 -1 ，右栈顶为 m。 两栈顶指针相邻时为栈满。两栈顶相向、迎面增长，栈顶指针指向栈顶元素。
[ 算法描述 ]

1) 栈初始化

int Init()  {
    S.top[0]=-1; 
    S.top[1]=m; 
    return 1; // 初始化成功
}

2) 入栈操作：

int push(stk S ,int i,int x) 
// i 为栈号， i=0 表示左栈， i=1 为右栈， x 是入栈元素。入栈成功返回 1，失败返回 0 
{
    if(i<0||i>1){
        cout<< “栈号输入不对 ”<<endl;exit(0);} 
    if(S.top[1]-S.top[0]==1) {
        cout<< “栈已满 ”<<endl;return(0);} 
    switch(i) {
        case 0: S.V[++S.top[0]]=x; return(1); break; 
        case 1: S.V[--S.top[1]]=x; return(1); 
    } 
}// push

3.退栈操作

ElemType pop(stk S,int i) 
//退栈。 i 代表栈号， i=0 时为左栈， i=1 时为右栈。退栈成功时返回退栈元素
//否则返回 -1 
{
    if(i<0 || i>1){cout<< “栈号输入错误 ”<<endl ； exit(0);} 
     switch(i) {
         case 0: 
             if(S.top[0]==-1) {
                 cout<< “栈空 ”<<endl ； return （ -1）； } 
            else return(S.V[S.top[0]--]); 
        case 1: 
            if(S.top[1]==m {
                cout<< “栈空 ”<<endl; return(-1);} 
            else return(S.V[S.top[1]++]); 
     } // switch 
} //算法结束

1. 判断栈空

int Empty(); 
{
    return (S.top[0]==-1 && S.top[1]==m); 
}

（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。（提示：将一半字符入栈）

[算法讨论 ]
请注意算法中两栈入栈和退栈时的栈顶指针的计算。左栈是通常意义下的栈，而右栈入栈操作时，其栈顶指针左移（减 1），退栈时，栈顶指针右移（加 1）。 （ 2）回文是指正读反读均相同的字符序列， 如“ abba”和“ abdba ”均是回文， 但“ good ”不是回文。试写一个算法判定给定的字符向量是否为回文。 (提示：将一半字符入栈 )
[ 题目分析 ]
将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较 ，直至栈空， 结论为字符序列是回文。 在出栈元素与串中字符比较不等时， 结论字符序列不是回文。 [ 算法描述 ]

#define StackSize 100 // 假定预分配的栈空间最多为 100 个元素
typedef char DataType;// 假定栈元素的数据类型为字符
typedef struct  {
    DataType data[StackSize]; 
    int top; 
}SeqStack; 
int IsHuiwen( char *t) 
{// 判断 t 字符向量是否为回文，若是，返回 1，否则返回 0 
    SeqStack s; 
    int i , len; 
    char temp; 
    InitStack( &s); 
    len=strlen(t); // 求向量长度
    for ( i=0; i<len/2; i++)// 将一半字符入栈
        Push( &s, t[i]); 
    while( !EmptyStack( &s)) 
    {// 每弹出一个字符与相应字符比较
        temp=Pop (&s); 
        if( temp!=S[i]) return 0 ;// 不等则返回 0 
        else i++; 
    } 
    return 1 ; // 比较完毕均相等则返回 1 
}

（3）设从键盘输入一整数的序列：a1, a2, a3, …, an，试编写算法实现：用栈结构存储输入的整数，当ai≠−1时，将ai进栈；当ai=−1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

#define maxsize 栈空间容量
void InOutS(int s[maxsize]) 
//s 是元素为整数的栈，本算法进行入栈和退栈操作。
{
    int top=0; //top 为栈顶指针，定义 top=0 时为栈空。
    for(i=1; i<=n; i++) //n 个整数序列作处理。
    18 
        {cin>>x); // 从键盘读入整数序列。
    if(x!=-1) // 读入的整数不等于 -1 时入栈。
    ｛ 
        if(top==maxsize-1)
            {cout<< “栈满” <<endl;exit(0);} 
        else s[++top]=x; //x 入栈。
    ｝
    else // 读入的整数等于 -1 时退栈。
    {
        if(top==0)
            {cout<< “栈空” <<endl;exit(0);} 
        else cout<< “出栈元素是” <<s[top--]<<endl;} 
    } 
}// 算法结束。

（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以“$” 作为输入结束，操作数之间用空格分隔，操作符只可能有+、−、*、/四种运算。例如：23434+2*$。

[ 题目分析 ]
逆波兰表达式 ( 即后缀表达式 ) 求值规则如下：设立运算数栈 OPND,对表达式从左到右扫 描 ( 读入 ) ，当表达式中扫描到数时， 压入 OPND栈。 当扫描到运算符时， 从 OPND退出两个数， 进行相应运算，结果再压入 OPND 栈。这个过程一直进行到读出表达式结束符 $，这时 OPND 栈中只有一个数，就是结果。
[ 算法描述 ]

float expr( ) 
// 从键盘输入逆波兰表达式，以‘ $’表示输入结束，本算法求逆波兰式表达式的值。
｛ 
    float OPND[30]; // OPND 是操作数栈。
    init(OPND); // 两栈初始化。
    float num=0.0; // 数字初始化。
    cin>>x;//x 是字符型变量。
    while(x!= ’$’)
    {
        switch 
         {
             case ‘0’<=x<=’9’:
                while((x>= ’0’&&x<=’9’)||x== ’. ’) // 拼数
                    if(x!= ’. ’) // 处理整数
                    {
                        num=num*10+ （ ord(x)- ord( ‘0’) ） ; cin>>x;
                    } 
                    else // 处理小数部分。
                    {
                        scale=10.0; cin>>x; 
                        while(x>= ’0’&&x<=’9’)
                            {num=num+(ord(x)- ord( ‘0’)/scale;
                        scale=scale*10; cin>>x; } 
                    }//else 
                push(OPND,num); num=0.0;// 数压入栈，下个数初始化
             case x= ‘ ’:break; // 遇空格，继续读下一个字符。
             case x= ‘+’:push(OPND,pop(OPND)+pop(OPND));break;
             case x= ‘ - ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; 
             case x= ‘*’:push(OPND,pop(OPND)*pop(OPND));break;
             case x= ‘ / ’ :x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; 
             default: // 其它符号不作处理。
         }// 结束 switch 
        cin>>x;// 读入表达式中下一个字符。
     }// 结束 while （ x！ =‘$’）
    cout<< “后缀表达式的值为” <<pop(OPND); 
}// 算法结束。

（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
① 下面所示的序列中哪些是合法的？
A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IIIOOIOO
② 通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

    
int Judge(char A[]) 
 // 判断字符数组 A 中的输入输出序列是否是合法序列。如是，返回 true ，否则返回
false 。
 {
     i=0; //i 为下标。
     j=k=0; //j 和 k 分别为 I 和字母 O 的的个数。
     while(A[i]!= ‘ 0’) // 当未到字符数组尾就作。
     {
         switch(A[i]) 
         {
             case ‘I ’: j++; break; // 入栈次数增 1。
             case ‘O’: k++; if(k>j){ 
                 cout<< “序列非法” <

    
//先定义链队结构 : 
typedef struct queuenode 
{
    Datatype data; 
    struct queuenode *next; 
}QueueNode; // 以上是结点类型的定义

typedef struct 
{
    queuenode *rear; 
}LinkQueue; // 只设一个指向队尾元素的指针    
    

    
void InitQueue( LinkQueue *Q) 
{ // 置空队：就是使头结点成为队尾元素
    QueueNode *s; 
    Q->rear = Q->rear->next;// 将队尾指针指向头结点
    while (Q->rear!=Q->rear->next)// 当队列非空，将队中元素逐个出队
    {
        s=Q->rear->next; 
        Q->rear->next=s->next; 
    }
    delete s; 
}// 回收结点空间

    

    
int EmptyQueue( LinkQueue *Q) 
{ // 判队空。当头结点的 next 指针指向自己时为空队
    return Q->rear->next->next==Q->rear->next; 
}     
    

    
void EnQueue( LinkQueue *Q, Datatype x) 
{ // 入队。也就是在尾结点处插入元素
    QueueNode *p=new QueueNode;// 申请新结点
    p->data=x; p->next=Q->rear->next;// 初始化新结点并链入
    Q-rear->next=p; 
    Q->rear=p;// 将尾指针移至新结点
}     
    

    
Datatype DeQueue( LinkQueue *Q) 
{// 出队 ,把头结点之后的元素摘下
    Datatype t; 
    QueueNode *p; 
    if(EmptyQueue( Q )) 
        Error("Queue underflow"); 
    p=Q->rear->next->next; //p 指向将要摘下的结点
    x=p->data; // 保存结点中数据
    if (p==Q->rear) 
    {// 当队列中只有一个结点时， p 结点出队后，要将队尾指针指向头结点
        Q->rear = Q->rear->next; 
        Q->rear->next=p->next; 
    } 
    else 
        Q->rear->next->next=p->next;// 摘下结点 p 
    delete p;// 释放被删结点
    return x; 
}     
    

    
SeQueue QueueInit(SeQueue Q) 
{// 初始化队列
    Q.front=Q.rear=0; Q.tag=0; 
    return Q; 
}     
    

    
SeQueue QueueIn(SeQueue Q,int e) 
{// 入队列
    if((Q.tag==1) && (Q.rear==Q.front)) 
        cout<

    
ElemType QueueOut(SeQueue Q) 
{// 出队列
    if(Q.tag==0) { 
        cout<

    
#define M 队列可能达到的最大长度
typedef struct 
{
    elemtp data[M]; 
    int front,rear; 
}cycqueue;     
    

    
elemtp delqueue ( cycqueue Q) 
 //Q 是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，
否则给出出错信息。
{
    if (Q.front==Q.rear) {
        cout<

（9）已知Ackermann函数定义如下： ① 写出计算Ack(m, n)的递归算法，并根据此算法给出Ack(2, 1)的计算过程。
② 写出计算Ack(m, n)的非递归算法。

    
int Ack(int m,n)
{
    if (m==0) return(n+1);
    else if(m!=0&&n==0) return(Ack(m-1,1)); 
    else return(Ack(m-1,Ack(m,m-1)); 
}// 算法结束
    

    
int Ackerman(int m, int n) 
{
    int akm[M][N];int i,j; 
    for(j=0;j

（10）已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：
① 求链表中的最大整数；
② 求链表的结点个数；
③ 求所有整数的平均值。

王道习题

    
int GetMax(LinkList p) 
{ 
    if(!p->next) 
        return p->data; 
    else 
    { 
        int max=GetMax(p->next); 
        return p->data>=max ? p->data:max; 
    } 
} 
    

    
int GetLength(LinkList p) 
{ 
    if(!p->next) 
        return 1; 
    else 
    { 
        return GetLength(p->next)+1; 
    } 
} 
    

    
double GetAverage(LinkList p , int n) 
{ 
    if(!p->next) 
        return p->data; 
    else 
    { 
        double ave=GetAverage(p->next,n-1); 
        return (ave*(n-1)+p->data)/n; 
    } 
}